/*
 * @Description: 双向链表回顾
 * @Author: Han_ruofei
 * @Date: 2022-07-09
 */
// 节点类型
class NodeList {
    constructor(val) {
        // 包含数据节点，前驱节点以及下一个节点
        this.data = val;
        this.pre = null;
        this.next = null;
    }
}
// 双向链表
class DoubleLinked {
    constructor() {
        this.length = 0;
        this.head = null;
        this.tail = null
    }
    // 向链表尾部添加元素
    appendNode(val) {
        if (val == undefined) return '缺少参数';
        let newNode = new NodeList(val)
        // 判断链表是否有数据
        if (this.head === null) {
            this.head = newNode;
            this.tail = newNode;
        }
        // 如果有的话，则向尾部添加
        else {
            this.tail.next = newNode;
            newNode.pre = this.tail;
            this.tail = newNode
        }
        this.length++;
        return this.displayList()
    }
    // 通过值来返回索引,双向链表可以从两个方向开始遍历
    getPositionByData(val) {
        let head = this.head;
        let tail = this.tail;
        let index = 0;

        while (head) {
            if (head.data === val) return index;
            head = head.next;
            if (tail.data === val) return this.length - 1 - index;
            tail = tail.pre;
            index++;
        }
        // 否则说明没有找到，返回null
        return null
    }
    // 通过给定索引来返回节点
    getNodeByPosition(position) {
        if (position >= this.length || position < 0) return false;
        // 算法优化，如果大于二分之一，就从尾节点开始遍历
        let middlePosition = Math.ceil(position / 2);
        // 当前节点
        let curNode = null;
        if (position >= middlePosition) {
            curNode = this.tail;
            let i = this.length - 1
            // 从后往前执行
            while (i > position) {
                curNode = curNode.pre;
                i--;
            }
        } else {
            curNode = this.head;
            while (position--) {
                curNode = curNode.next
            }
        }
        return curNode
    }
    getNodeByData(val) {
        // 头指针和尾指针
        let headNode = this.head;
        let tailNode = this.tail;

        while (headNode) {
            if (headNode.data == val) return headNode;
            if (tailNode.data == val) return tailNode;
            headNode = headNode.next;
            tailNode = tailNode.pre;
        }
        // 没有找到就返回null
        return null
    }
    // 通过索引来返回节点的值
    getDataByPosition(position) {
        if (position >= this.length || position < 0) return false;
        let middlePosition = Math.floor(position / 2);
        let curNode = null;
        if (position > middlePosition) {
            curNode = this.tail;
            let i = this.length - 1;
            while (i > position) {
                curNode = curNode.pre;
                i--
            }
        } else {
            curNode = this.head;
            while (position--) {
                curNode = curNode.next
            }
        }
        return curNode.data
    }
    // 指定位置插入元素，不指定默认尾部插入
    insertNode(position, val) {
        if (arguments.length === 1) throw new Error('缺少参数');

        if (position >= this.length || position < 0) return '索引越界'
        // 判断是不是尾部插入
        if (position === this.length - 1) {
            // 尾部插入
            return this.appendNode(val);

        }
        // 判断是不是头部插入
        else if (position === 0) {
            // 判断是否有头节点
            if (this.head === null) {
                this.appendNode(val)
            } else {
                // 有头节点的头部插入
                let headNode = new NodeList(val);
                headNode.next = this.head;
                this.head.pre = headNode;
                this.head = headNode;
            }
        }
        // 中间插入，大多数情况
        else {
            let newNode = new NodeList(val);
            let curNode = this.getNodeByPosition(position);
            newNode.next = curNode;
            newNode.pre = curNode.pre;
            curNode.pre.next = newNode;
            curNode.pre = newNode;
        }
        this.length++;
        return true
    }
    // 根据索引来移除节点
    removeNodeByPosition(position) {
        // 异常判断
        if (position > this.length - 1 || position < 0) return null;
        // 头部删除
        let curNode = this.getNodeByPosition(position)

        if (position = 0) {
            this.head = this.head.next;
            this.head.pre = null;
        } else if (position === this.length - 1) {
            this.tail = this.tail.pre;
            this.tail.next = null;
        }
        // 移除中间元素
        else {
            let preNode = curNode.pre;
            let nextNode = curNode.next;
            preNode.next = nextNode;
            nextNode.pre = preNode;
        }
        this.length--;
        return curNode
    }
    // 将链表中的内容格式化打印，默认参数为空格
    displayList(join = ' ') {
        let curNode = this.head;
        let str = '';
        while (curNode) {
            // 最后一个拼接的后面不用加连接的内容
            curNode.next !== null ? str += curNode.data + join : str += curNode.data
            curNode = curNode.next;
        }
        return str
    }

}
let linkList = new DoubleLinked()
linkList.appendNode('apple');
linkList.appendNode('banana');
linkList.appendNode('peach');
linkList.appendNode('7777')
linkList.getDataByPosition(2)
linkList.getPositionByData('apple')
console.log(linkList.displayList());